#include <bits/stdc++.h>
using namespace std;
const int N=105;
struct Edge{
    int v,next;
}edge[N<<1];
int cnt,head[N];
int p[N],b[N];
int n,m,u,v;
int dp[N][N];
void init(){
    cnt=0;
    memset(head,-1,sizeof(head));
}
void addEdge(int u,int v){
    edge[cnt]=Edge{v,head[u]};
    head[u]=cnt++;
    edge[cnt]=Edge{u,head[v]};
    head[v]=cnt++;
}
void dfs(int u,int pa){
    //需要的人数
    int c=(p[u]+19)/20;
    if(c>m){
        return;
    }
    for(int i=c;i<=m;i++){
        dp[u][i]=b[u];
    }
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==pa){
            continue;
        }
        //子节点信息来更新父节点信息
        dfs(v,u);
        //枚举放置的人数 u放置j-k人 v放置k人 相当于u所在的整个子树放置j人
        for(int j=m;j>=c;j--){
            for(int k=0;k<=j-c;k++){
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
            }
        }
    }
    //注意没这个会wa
    //至少要放1个人，所以把0的状态更新到1上，因为既然0个人都能达到这状态，1个人当然也可以
    if(dp[u][0]>0){
        dp[u][1]=max(dp[u][1],dp[u][0]);
        dp[u][0]=0;
    }
}
int main(void){
    while(~scanf("%d%d",&n,&m)){
        if(n==-1 && m==-1){
            break;
        }
        init();
        memset(dp,0,sizeof(dp));
        memset(p,0,sizeof(p));
        memset(b,0,sizeof(b));
        for(int i=1;i<=n;i++){
            scanf("%d%d",&p[i],&b[i]);
        }
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&u,&v);
            addEdge(u,v);
        }
        dfs(1,0);
        //枚举根节点放的个数
        int ans=0;
        for(int i=1;i<=m;i++){
            ans=max(ans,dp[1][i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}